package org.algorithm.wE1.链表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Lvpin
 * @date 2022/2/15 19:49
 */
public class 三数之和 {

    public static void main(String[] args) {
        int[] arr = {1,-2,3,-4,5,-6,-2,1,-4,-5,-2,10,9,-8};
        int target = 5;
        System.out.println(threeSum2(arr,target));
    }
    public static List<List<Integer>> threeSum2(int[] arr,int target){
        if(arr == null || arr.length<3){
            return null;
        }
        List<List<Integer>> list = new ArrayList<>();
        int len =  arr.length;
        Arrays.sort(arr);
        for (int i = 0; i <len ; i++) {
            if(arr[i]>target){
                break;
            }
            if(i>0&&arr[i] == arr[i-1]){
                continue;
            }
            int left = 0;
            int right = len-1;
            while (left<right){
                int sum = arr[left]+arr[i]+arr[right];
                if(sum == target){
                    list.add(Arrays.asList(arr[left],arr[i],arr[right]));
                    while (left<right && arr[left]==arr[left+1]){
                        left++;
                    }
                    while(left<right && arr[right] == arr[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }else if(sum>target){
                    right--;
                }
                if(sum<target){
                    left++;
                }

            }
        }
        return list;
    }


















    private static List<List<Integer>> threeSum(int[] arr,int target){
        if(arr == null || arr.length < 3){
            throw new IllegalArgumentException("arr.length < 3.");
        }
        List<List<Integer>> lists = new ArrayList<>();
        int len = arr.length;
        Arrays.sort(arr);
        for (int i = 0; i <arr.length ; i++) {
            if(arr[i] > target){
                break;
            }
            if(i > 0 && arr[i] == arr[i-1]){
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            while(left<right){
                int sum = arr[i] + arr[left] + arr[right];
                if(sum == target){
                    lists.add(Arrays.asList(arr[i],arr[left],arr[right]));
                    while(left<right&&arr[left] == arr[left+1]){
                        left++;
                    }
                    while (left<right&&arr[right] == arr[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }else if(sum<target){
                    left++;
                }else {
                    right--;
                }
            }
        }
        return lists;
    }
}
